But we've seen that greedy search is not optimal. It's not even complete. So we're now going

to come to a search strategy which is called A star search, which is a variant of greedy

search, which makes this optimal.

And the idea is the following.

Let me tell you this loop story with different protagonists.

Say you do the following experiment.

You have a fence, you have a bowl of food, and now it becomes difficult.

A chicken.

I'll write it down because you otherwise might not see. I'm not very good at making chickens,

but this is a chicken.

Now chickens do greedy search. They can't do more.

So what do they do? They see the bowl of food, say, ah, great food.

They go here.

Then they see, oops, problem.

Let's go here.

Ah, I'm getting further away.

Oh God, oh God, oh God.

Let's go back.

And what they do is they run into a loop here.

You can actually do this experiment if you have a long enough fence that they can't fly

over or something like this, then they'll just go back and forth.

Typical greedy search behavior.

Now what would you do in the same situation?

You would probably say, oh, I've been here seven times.

You would get more and more annoyed.

That's very important.

Getting annoyed is very important in this problem, which says, oh, I'm not going to

do this anymore because you're so annoyed.

So you would probably do something like this, oh, and get around the fence.

That's what A star search does.

You basically don't do greedy search on the original heuristic functions, but you add

an annoyance clause.

So what you do is, given a heuristic, you make a new heuristic, F of M, by just adding

the past path costs.

That's kind of like annoyance.

You go here, you accumulate path costs, which makes you annoyed, more annoyed, and boom.

So if you do greedy or best first search with this composite heuristic function, that actually

turns out to be extremely good, provably good.

But before you laugh too much about the chicken, many people, including myself, imagine you

have to catch a train and you take your bike to the station, very important train or plane,

say, to South Africa to make it expensive.

You can't find your keys.

What I do is I look here and I look there and say, maybe I lost it here, I look there,

get a little more panicky all the time and start doing exactly what the chicken does,

searching in the old places.

Fortunately, my wife keeps calm and says, Michael, don't search there again.

You've already been there.

And then usually we find the key, eventually, most of the time before the plane leaves.

But when you're very much under stress and the time barrier, because the time gets shorter

and shorter, you revert to simpler and simpler strategies.